Manual Big-O Analysis
Beginner & Interview Summaries
When the input size n doubles, the runtime grows by approximately 1.89×, which suggests performance closer to O(n).
Interview: linear_search has an estimated time complexity of O(n) and space complexity of O(1). For recursive implementations that halve the search space (e.g., binary search), space is O(log n) due to recursion depth; iterative versions are O(1) space.
When the input size n doubles, the runtime grows by approximately 1.08×, which suggests performance closer to O(log n).
Interview: binary_search has an estimated time complexity of O(n) and space complexity of O(1). For recursive implementations that halve the search space (e.g., binary search), space is O(log n) due to recursion depth; iterative versions are O(1) space.
Runtime Chart
Runtime Table (mean ± 95% CI)
| n | linear_search | binary_search |
|---|---|---|
| 1000 | 15.27 µs ± 5.88 µs | 1.74 µs ± 139.94 ns |
| 2000 | 29.49 µs ± 12.97 µs | 1.91 µs ± 109.11 ns |
| 4000 | 53.80 µs ± 20.77 µs | 2.38 µs ± 298.79 ns |
| 8000 | 151.18 µs ± 33.37 µs | 2.28 µs ± 126.90 ns |
| 16000 | 234.90 µs ± 76.87 µs | 2.35 µs ± 147.68 ns |
| 32000 | 311.75 µs ± 92.81 µs | 2.47 µs ± 185.25 ns |
Peak Memory Chart
Memory Table (mean ± 95% CI)
| n | linear_search | binary_search |
|---|---|---|
| 1000 | 226.91 B ± 11.34 B | 176.00 B ± 0.00 B |
| 2000 | 226.91 B ± 11.34 B | 188.73 B ± 9.82 B |
| 4000 | 232.00 B ± 0.00 B | 204.00 B ± 0.00 B |
| 8000 | 232.00 B ± 0.00 B | 204.00 B ± 0.00 B |
| 16000 | 232.00 B ± 0.00 B | 204.00 B ± 0.00 B |
| 32000 | 232.00 B ± 0.00 B | 204.00 B ± 0.00 B |
Comparison Summary
Best/worst runtime at each n (lower is better). Mean ranks summarize performance across all n.
| n | Best Runtime | Worst Runtime | Mean Ranks |
|---|---|---|---|
| 1000 | binary_search | linear_search | linear_search: 2.00 binary_search: 1.00 |
| 2000 | binary_search | linear_search | linear_search: 2.00 binary_search: 1.00 |
| 4000 | binary_search | linear_search | linear_search: 2.00 binary_search: 1.00 |
| 8000 | binary_search | linear_search | linear_search: 2.00 binary_search: 1.00 |
| 16000 | binary_search | linear_search | linear_search: 2.00 binary_search: 1.00 |
| 32000 | binary_search | linear_search | linear_search: 2.00 binary_search: 1.00 |
Mean Runtime Comparison (bar)
Bar chart placeholder: you can render an additional Plotly bar chart here comparing means per function.